7799. Наурыз Cup 2015

Скоро состоится командное соревнование «Наурыз Cup 2015». Команда должна состоять ровно из двух участников. Аманчик сильно хочет в нем участвовать. Он достал список всех 2 * n (1 ≤ n ≤ 10⁵) участников включая себя. У каждого участника есть свой рейтинг.

Рейтинг команды это средний рейтинг двух участников. Чем выше рейтинг команды тем выше его место. Команда занимает место под номером k + 1, если есть ровно k команд, рейтинг которых строго больше.

Из всевозможных разбиений, какое самое высокое и самое низкое место может занять команда Аманчика. Аманчик участник под номером 1.

Вход. Первая строка содержит целое число n. Следующая строка содержит 2 * n целых чисел a_i (1 ≤ a_i ≤ 10⁵, 1 ≤ i ≤ 2 * n), разделенных пробелами.

Выход. Выведите два числа самое высокое и самое низкое место.

Пример входа	Пример выхода
3 999 3 1 2 1000 1	1 2

Пояснение

Если мы разобьем участников следующим образом (999, 2) (3, 1) (1000, 1) то команда Аманчика (999, 2) и команда (1000, 1) возьмут первые места, а команда (3, 1) возьмет третье место. А если мы разобьем следующим образом (999, 1) (1000, 2) (3, 1) то команда Аманчика возьмет второе место. Из всевозможных разбиений, указанные выше будут соответствовать самым высоким и самым низким местам.

РЕШЕНИЕ

жадность

Анализ алгоритма

Отсортируем рейтинги участников не включая рейтинг Аманчика. Для нахождения самого высокого места Аманчику в команду следует включить игрока с наивысшим рейтингом. Для нахождения самого низкого места Аманчику в команду следует включить игрока с самым низким рейтингом.

Пусть a₁, a₂, … , a_n – рейтинги участников, где a₁ – рейтинг Аманчика, a₂ ≤ … ≤ a_n (умножим предварительно n на 2 так чтобы n равнялось числу участников, а не количеству пар)

Поиск наивысшего места. Рейтинг команды Аманчика составит aman = a₁ + a_n. Занесем остальные числа a₂, … , a_n-1 в мультимножество. Их следует разбить на пары так чтобы рейтинг как можно большего количества этих пар был строго меньше aman. Воспользуемся жадным подходом.

Для самого рейтингового участника ищем такого другого участника с таким наибольшим рейтингом, чтобы суммарный рейтинг пары был строго меньше aman. Самый рейтинговый участник находится в конце множества (числа в нем отсортированы по неубыванию). Второго участника ищем бинарным поиском во множестве, а именно при помощи функции upper_bound. Если такой участник существует, то пара найдена и ее участников удаляем из мультимножества. Если такого участника не существует, то существует пара которая окажется сильнее команды Аманчика и в таком случае первому участнику лучше поставить в пару того, кто имеет наивысший рейтинг из оставшихся.

Продолжаем таким образом поиск пар участников пока мультимножество не окажется пустым.

Реализация алгоритма

Рейтинг участников храним в массиве а. Объявим рабочее мультимножество и итератор на него.

#define MAX 200100

int a[MAX];

multiset<int> st;

multiset<int>::iterator iter;

Поиск возможного наивысшего места.

int GetMax(void)

{

В команду к Аманчику следует включить игрока с наивысшим рейтингом.

int amans_pair = a[1] + a[n];

Занесем все остальные рейтинги в мультимножество (не принадлежащие участникам из команды Аманчика).

for(i = 2; i <= n - 1; i++)

st.insert(a[i]);

В переменной pos ищем наивысшее возможное место команды Аманчика.

int pos = 1;

while(!st.empty())

{

Занесем в val максимальный рейтинг участника. Удалим участника с максимальным рейтингом.

iter = st.end(); iter--;

int val = *iter;

st.erase(iter);

Ищем участника, рейтинг которого вместе с val будет не больше силы команды Аманчика.

iter = st.upper_bound(amans_pair - val);

if (iter == st.begin())

{

Если такого не существует, то с val в команду берем участника с наибольшим рейтингом. Удаляем его из мультимножества.

Появилась команда с рейтингом выше команды Аманчика. Рейтинг команды Аманчика понижается на 1 (pos++).

pos++;

iter = st.end(); iter--;

st.erase(iter);

continue;

}

Если такой участник существует, то составляем из него и участника с рейтингом val пару и удаляем из мультимножества.

iter--;

st.erase(iter);

}

return pos;

}

Поиск возможного наименьшего места.

int GetMin(void)

{

В команду к Аманчику следует включить игрока с самым низким рейтингом.

int amans_pair = a[1] + a[2];

Занесем все остальные рейтинги в мультимножество (не принадлежащие участникам из команды Аманчика).

for(i = 3; i <= n; i++)

st.insert(a[i]);

int pos = 1;

while(!st.empty())

{

int val = *st.begin();

st.erase(st.begin());

iter = st.upper_bound(amans_pair - val);

if (iter == st.end())

st.erase(st.begin());

else

{

st.erase(iter);

pos++;

}

}

return pos;

}

Основная часть программы. Читаем рейтинги. Сортируем их кроме первого – рейтинга Аманчика.

scanf("%d", &n); n = 2*n;

for(i = 1; i <= n; i++)

scanf("%d",&a[i]);

sort(a + 2, a + n + 1);

Выводим ответ.

printf("%d %d\n",GetMax(),GetMin());